package com.study.algorithm.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 101. 对称二叉树
 */
public class IsMirror {
    //方法一：递归；深度优先
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        // 两个都为空，对称
        if (left == null && right == null) return true;

        // 一个为空一个不为空，不对称
        if (left == null || right == null) return false;

        // 值不相等，不对称
        if (left.val != right.val) return false;

        // 递归检查：左左 vs 右右，左右 vs 右左
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }


    //方法二：迭代 广度优先
    public boolean isSymmetric1(TreeNode root) {
        if (root == null) return true;

        // 使用队列进行BFS遍历
        Queue<TreeNode> queue = new LinkedList<>();
        // 将左右子树作为一对加入队列
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            // 每次取出两个节点进行比较
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            // 两个都为空，继续检查下一对
            if (left == null && right == null) {
                continue;
            }
            // 一个为空一个不为空，不对称
            if (left == null || right == null) {
                return false;
            }
            // 值不相等，不对称
            if (left.val != right.val) {
                return false;
            }

            // 关键：按镜像顺序加入子节点对
            // 左左 vs 右右
            queue.offer(left.left);
            queue.offer(right.right);

            // 左右 vs 右左
            queue.offer(left.right);
            queue.offer(right.left);
        }

        return true;
    }
}
